/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***插入排序                   P62              ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
#include <random>
#include <ctime>
#include <cstdlib>

using std::endl;
using std::cout;
#define SIZE 80000


void printArr(int *arr, int size)
{
    for(int i=0;i<size;i++)
    {
        std::cout<<arr[i]<<"\t";
    }
    std::cout<<std::endl;
}
//选择排序算法
void insertSort(int *arr, int size)
{
    //
    int insertIndex=0;
    //从第1个位置开始，选择合适的位置，进行插入
    for(int i=1;i<size;i++){
        insertIndex=i-1;
        int temp=arr[i];
        //循环比较，确定插入的位置   
        while((temp<arr[insertIndex])&&(insertIndex>=0)){
            //当满足循环条件的时候，需要扫描到的数  逐个移动到右边
            arr[insertIndex+1]=arr[insertIndex];
            //插入位置的下标，左移
            insertIndex--;
        }
        arr[insertIndex+1]=temp;
    }
}

int main(int argc, char ** argv)
{
    srand(time(NULL));
    int* arr=new int[SIZE];
    for(int i=0;i<SIZE;i++){
        arr[i]=rand()%SIZE;
    }
    time_t start=time(NULL);
    cout<<"start time="<<start<<endl;
    insertSort(arr,SIZE);
    //printArr(arr,SIZE);
    time_t end=time(NULL);
    cout<<"end time="<<end<<endl;
    delete[] arr;
    return 0;
}